package main

import (
	"fmt"
)

func main() {
	M := [][]int{
		{1, 0, 0, 1},
		{0, 1, 1, 0},
		{0, 1, 1, 1},
		{1, 0, 1, 1}}
	height := findCircleNum(M)

	fmt.Println(height)
}

type UF struct {
	parent []int
	rank   []int
	count  int
}

func NewUF(n int) UF {
	var parent = make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}
	return UF{parent: parent, count: n, rank: make([]int, n)}
}

func findCircleNum(M [][]int) int {
	rowLen := len(M)
	UFObj := NewUF(rowLen)
	for i, _ := range M {
		for j, _ := range M {
			if M[i][j] == 1 && i != j {
				UFObj.union(i, j)
			}
		}
	}
	return UFObj.count
}

func (this *UF) union(p int, q int) {
	pLink := this.find(p)
	qLink := this.find(q)
	if pLink == qLink {
		return
	}
	//按秩合并,解决树失衡
	if this.rank[p] > this.rank[q] {
		this.parent[qLink] = pLink
		this.rank[q] += 1
	} else {
		this.parent[pLink] = qLink
		this.rank[p] += 1
	}
	this.count -= 1
}

func (this *UF) find(i int) int {
	for this.parent[i] != i {
		// 进行路径压缩 ，找到代表人
		this.parent[i] = this.parent[this.parent[i]]
		i = this.parent[i]
	}
	return i
}

func gridDfs(grid [][]int, i int, j int) {
	rows := len(grid)
	cols := len(grid[0])

	if i < 0 {
		return
	}
	if j < 0 {
		return
	}
	if i >= rows {
		return
	}
	if j >= cols {
		return
	}
	if grid[i][j] == 0 {
		return
	}

	grid[i][j] = 0

	// up
	gridDfs(grid, i-1, j)
	// down
	gridDfs(grid, i+1, j)
	// right
	gridDfs(grid, i, j+1)
	// left
	gridDfs(grid, i, j-1)
	return
}

func findCircleNum2(M [][]int) int {
	rows := len(M)
	if rows == 0 {
		return 0
	}
	cols := len(M[0])
	if cols == 0 {
		return 0
	}
	circleNum := 0
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if M[i][j] == 1 {
				circleNum++
				gridDfs(M, i, j)
			}
		}
	}
	return circleNum
}

// func findCircleNum1(M [][]int) int {
// 	N := len(M)
// 	if N == 0 {
// 		return 0
// 	}
// 	circleNum := 0
// 	ufs := makeSet(N)
// 	for i := 0; i < N; i++ {
// 		for j := 0; j < N; j++ {
// 			if M[i][j] == 1 {
// 				circleNum++
// 				gridDfs(M, i, j)
// 			}
// 		}
// 	}

// 	return circleNum
// }

// UnionFindSet Union Find Set
type UnionFindSet struct {
	parent int
	val    int
}

func makeSet(size int) *UnionFindSet {
	return &UnionFindSet{}
}

// Set set
func (u *UnionFindSet) Set() {

}

// Find find
func (u *UnionFindSet) Find() {

}
